/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-07
 * Time: 9:10
 */
public class NumMatrix {
    // 二维前缀和
    private int[][] sum;
    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        // sum[i][j] 表示 从[0][0] 到 [i-1][j-1] 的前缀和
        // 多开辟一行和一列, 可以不用考虑 下标越界的情况
        this.sum = new int[row + 1][col + 1];
        // 并不用像 dp 一样需要初始化
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 前缀和递推公式
                // 这里的公式类似于 通过一个小的矩形求包含这个小矩形的更大的矩形的面积
                sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 多开辟了一行和一列, 可以不用考虑 下标越界的情况
        return sum[row2+1][col2+1] - sum[row1][col2+1] - sum[row2+1][col1] + sum[row1][col1];
    }
}
